home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / pascal / btree4.zip / BTREE4.DOC next >
Text File  |  1988-01-17  |  26KB  |  661 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.                                   BTREE4
  29.  
  30.                 a Shareware Unit for Turbo Pascal ver. 4.0
  31.  
  32.                     for Data and Index file management
  33.  
  34.  
  35.                     Copyright (c) 1988 by W. Lee Passey
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.                              Pass-Key Software
  48.                             119 MacArthur Ave.
  49.                          Salt Lake City, UT  84115
  50.                           (801) 486-9239 (voice)
  51.                           (801) 485-7211 (data) 
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.      BTree4 is  a separately  compiled unit  for Turbo  Pascal ver. 4.0 from
  75. Borland International, Inc. BTree4  may be  linked to  a user's  source pro-
  76. grams,  and  will  performs  all  of  the  same B-tree indexing functions as
  77. Borland's Database Toolbox.
  78.  
  79.      This file contains general information about BTree4, an  annotated copy
  80. of the  interface segment  describing all variables and procedures available
  81. to calling procedures, and licensing and  registration information.   PLEASE
  82. READ THIS FILE COMPLETELY BEFORE ATTEMPTING TO USE BTREE4.
  83.  
  84. BTree4  has  been  designed  to  be as compatible as possible with Borland's
  85. Database Toolbox, but it  is not  a modification  of Borland's  source code;
  86. rather it  is a whole new set of procedures and functions using a compatible
  87. calling interface, but a wholly different memory storage  technique.  BTree4
  88. does not require any pre-defined constants or initializaton sequence, as all
  89. data storage, including the index page  stack, is  created as  needed on the
  90. heap.
  91.  
  92.      For maximum  flexibility, the BTree4 routines will not halt the program
  93. for any IO or heap full errors.  If an error is detected, the global boolean
  94. variable 'OK'  is set to false, and the global integer variable 'IOError' is
  95. set equal to the IO error code.   If the  error was  caused by  the unavail-
  96. ability of heap memory, 'IOError' will be set to -1.
  97.  
  98.      Disk  IO  errors  must  be  resolved  by the programmer, however memory
  99. allocation errors can usually  be  resolved  by  the  use  of  the procedure
  100. 'CheckMem'   in   conjunction   with   the   global  variable  'MaxPageMem.'
  101. 'MaxPageMem' should be set by the programmer to  the maximum  amount of heap
  102. memory which  will be allocated for the index page stack.  If the page stack
  103. attempts to exceed this amount of allocated memory,  little used  pages will
  104. be discarded from memory until the page stack is again under the limit.  The
  105. program expects that the amount of memory available will never  be less than
  106. the value stored in 'MinPageMem', and the stack size will never be decreased
  107. to less than that  value; thus,  'MaxPageMem' should  always be  larger than
  108. 'MinPageMem.'
  109.  
  110.      Both 'MaxPageMem'  and 'MinPageMem'  can be dynamically assigned values
  111. at any time during the operation of the program.  If more  dynamic memory is
  112. needed,  the  page  stack  can  be  reduced in size by reducing the value of
  113. 'MaxPageMem' (and 'MinPageMem', if necessary) and then calling CheckMem with
  114. a zero  parameter.  The only restriction is that 'MinPageMem' must always be
  115. large enough to hold one page from each  level of  the tree,  plus one extra
  116. page.  
  117.  
  118.      In  addition  to  the  page  stack,  each open data file and index file
  119. allocates for itself an IO buffer equal in size to the file's record length,
  120. and each  index file  allocates an extra page buffer which is the same size.
  121. These buffers are de-allocated  only by  closing the  associated file.   The
  122. record length  for index  files is  equal to  5 + (number of keys per page X
  123. (key length + 9)).
  124.  
  125.      What follows is a copy  of  the  BTree4  interface  section,  with each
  126. procedure and significant variable annotated as to its function and use.
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140. {$I-,V-}
  141.  
  142. unit btree4;                      { VERSION 1.0 }
  143.                                   { Copyright (c) 1988 by W. Lee Passey }
  144. interface
  145.  
  146. type
  147.   MaxString   = string[255];
  148.   bufarray    = array [1..80] of byte;
  149.   Str80       = string[80];
  150.  
  151.   PagePtr     = ^PageHeader;
  152.   KeyListPtr  = ^KeyList;
  153.  
  154.   DataFile    = record
  155.     case byte of
  156.       0 : (F      : file);
  157.       1 : (Handle,
  158.            Mode,
  159.            RecSize    : word;
  160.            Private    : array [1..26] of byte;        { reserved by TP4 }
  161.            FirstFree,         { the first available record in the file  }
  162.            NumberFree : longint;   { the number of records deleted and
  163.                                      therefore available for use        }
  164.            RecLength  : word;      { the length of records in this file }
  165.            KeysPerPage,            { if an index file, the maximum number
  166.                                      of keys which may be put on a page }
  167.            KeyLength  : byte;      { if an index file, the maximum
  168.                                      length of a key                    }
  169.            FirstPage  : longint;   { if an index file, the number of the
  170.                                      record which is the root page      }
  171.            FileName   : array [1..80] of char;
  172.            Buffer     : ^BufArray);{ pointer to a buffer on the heap,
  173.                                      used with this file, whose size is
  174.                                      identical to the record length     }
  175.            end;
  176.  
  177.   IndexFile   = record
  178.     DF        : DataFile;
  179.     RootPage  : PagePtr;           { a pointer to the root page, if it
  180.                                      is in memory                       }
  181.     KeySize,                       { the size of a key record, on the
  182.                                      heap, for keys in this file        }
  183.     ItemSize  : word;              { the size of a key, its reference
  184.                                      and record pointer, in this file   }
  185.     SavePage  : PagePtr;
  186.     SaveKey   : KeyListPtr;
  187.     SaveRec   : longint;
  188.     PageBuffer: ^BufArray;        { pointer to a buffer on the heap,
  189.                                     used with this file, whose size is
  190.                                     identical to the record length, and
  191.                                     which is used for packing and
  192.                                     unpacking pages to and from the disk
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.                                     and memory.                         }
  206.     end;
  207.  
  208. (*   Like Borland's Database Toolbook, each file use by BTree4 must be
  209. declared either as a DataFile or an IndexFile.  *)
  210.  
  211.   PageHeader  = record
  212.     NextPage,                     { these two pointers link the pages   }
  213.     PrevPage,                     { into a two-way linked list in memory
  214.                                     each time a page is used it is placed
  215.                                     back at the head of this list       }
  216.     ParentPage,                   { a pointer to this page's parent page
  217.                                     which should be in memory           }
  218.     GreaterPage : PagePtr;        { a pointer to a page on a lower level
  219.                                     containing keys greater than all
  220.                                     keys on this page, if in memory     }
  221.     GreaterRec,                   { the disk record number of the page
  222.                                     which goes in GreaterPage           }
  223.     RecNum      : longint;        { the disk record number of this page }
  224.     FilePtr     : ^IndexFile;     { points to the file variable of the
  225.                                     file which this page comes from     }
  226.     ParentKey,                    { the key record from the parent page
  227.                                     which contains the key which is one
  228.                                     greater than all the keys on this
  229.                                     page.  if this pointer is nil, you
  230.                                     must go up another page; if this is
  231.